#define _CRT_SECURE_NO_WARNINGS
//运用除留余数法作为哈希函数及差值解决法解决哈希冲突解决法、设计哈希表。*/
//程序构思：             
//依除留余数法将数据存储至哈希表中，发生哈希冲突时以差值解决法解决。
//除留余数法:                                                      
//Address=Key % Array_Size                                     
//差值解决法：                                               
//New_Address=(Old_Address+Offset)%Array_Siae                 
///数据查找时，同时也先用除留余数法运算出数据地址，
//若找不到运用差值法找出下一个数据地址，直到数据全查找完为止。

#include<stdio.h>
#define Max 6
#define HashMax 7

int Data[Max] = { 12,160,219,522,725,9997 }; //数据数组
int HashTab[HashMax];
int Counter = 1;                           //计数器

int Hash_Mod(int Key)                    //哈希函数之除留余数法
{
    return  Key % HashMax;                             //返回，键值除以哈希表大小取余数
}

int Collision_Offset(int Address)        //差值哈希冲突解决法 
{
    int offset = 3;                        //设差值为3
    return  (Address + offset) % HashMax;                         //返回，旧地址加差值除以哈希表大小取余数*/
}

int Create_Hash(int Key)                //建立哈希表 
{
    int a = Hash_Mod(Key);
    while (HashTab[a] != 0) {
        a = Collision_Offset(a);
        if (a >= HashMax)
            return 0;
    }
    HashTab[a] = Key;

    return 1;
}

int Hash_Search(int Key)         //哈希查找法
{
    int Address;                 //数据地址

    Counter = 0;
    Address = Hash_Mod(Key);       //调用哈希函数
    while (Counter < HashMax)
    {
        Counter++;
        if (HashTab[Address] == Key)
            return 1;
        else
            Address = Collision_Offset(Address);  //调用冲突解决法
    }
    return 0;
}

int main()
{
    int    KeyValue = 0;     //欲查找数据变量
    int    Index;        //输入数据索引
    int    i;

    Index = 0;

    printf("原始的数据为：");         //输出输入数据
    for (i = 0; i < Max; i++)
        printf("[%d]", Data[i]);
    printf("\n");

    for (i = 0; i < HashMax; i++)            //哈希表初始化
        HashTab[i] = 0;

    while (Index < Max)
    {
        if (Create_Hash(Data[Index]))
            printf("哈希存储成功!!\n");        //哈希建立成功
        else
            printf("哈希存储失败!!\n");        //哈希建立失败
        Index++;
    }
    for (i = 0; i < HashMax; i++)                   //输出哈希数据
    {
        printf("[%d]", HashTab[i]);
    }
    printf("\n");

    while (KeyValue != -1)                         //输入-1结束程序
    {
        printf("请输入要查找的值：");
        scanf("%d", &KeyValue);

        if (Hash_Search(KeyValue))
            printf("查找次数 = %d 次，查找成功！\n", Counter);//输出查找次数
        else
            printf("查找失败，没有这个数据！\n");             //输出没有找到数据
    }
    return 0;
}
